#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 100000

// See slide 7, chapter 6
void InsertionSort(int *A, int n) {
  for(int p = 1; p <= n - 1; p++) {
    int key = A[p];
    int i = p - 1;
    while(i >= 0 && A[i] > key) {
      A[i + 1] = A[i];
      i--;
    }
    A[i + 1] = key;
  }
}

////////////////////////////////////////////////////////////

// See slide 16, chapter 6
void Merge(int *A, int left, int center, int right) {
  int B[right - left + 1];
  int i1 = left, i2 = center + 1, i = 0;
  
  while(i1 <= center && i2 <= right) {
    if(A[i1] < A[i2]) {
      B[i++] = A[i1++];
    } else {
      B[i++] = A[i2++];
    }
  }
  while(i1 <= center) {
    B[i++] = A[i1++];
  }
  while(i2 <= right) {
    B[i++] = A[i2++];
  }
  for(i = 0; i < right - left + 1; i++) {
    A[left + i] = B[i];
  }
}

// See slide 15, chapter 6
void MergeSort(int *A, int left, int right) {
  if(left >= right) {
    return;
  }
  int center = (left + right) / 2;
  MergeSort(A, left, center);
  MergeSort(A, center + 1, right);
  Merge(A, left, center, right);
}

////////////////////////////////////////////////////////////

int main(void) {
  int A1[SIZE], A2[SIZE];

  // Initialize pseudo-random number genrator:
  srand(time(NULL));
  // And fill in the arrays:
  for(int i = 0; i < SIZE; i++) {
    A2[i] = A1[i] = rand();
  }

  clock_t start = clock();
  InsertionSort(A1, SIZE);
  clock_t end = clock();
  printf("Insertion Sort: %f ms\n", 1000.0 * (double)(end - start) / CLOCKS_PER_SEC);

  start = clock();
  MergeSort(A2, 0, SIZE - 1);
  end = clock();
  printf("Merge Sort: %f ms\n", 1000.0 * (double)(end - start) / CLOCKS_PER_SEC);

  return 0;
}
